Search results for "Congruence relation"
showing 9 items of 9 documents
All congruences below stability-preserving fair testing or CFFD
2020
AbstractIn process algebras, a congruence is an equivalence that remains valid when any subsystem is replaced by an equivalent one. Whether or not an equivalence is a congruence depends on the set of operators used in building systems from subsystems. Numerous congruences have been found, differing from each other in fine details, major ideas, or both, and none of them is good for all situations. The world of congruences seems thus chaotic, which is unpleasant, because the notion of congruence is at the heart of process algebras. This study continues attempts to clarify the big picture by proving that in certain sub-areas, there are no other congruences than those that are already known or …
The dual equivalence of equations and coequations for automata
2015
The transition structure α : X ? X A of a deterministic automaton with state set X and with inputs from an alphabet A can be viewed both as an algebra and as a coalgebra. We use this algebra-coalgebra duality as a common perspective for the study of equations and coequations. For every automaton ( X , α ) , we define two new automata: free ( X , α ) and cofree ( X , α ) representing, respectively, the greatest set of equations and the smallest set of coequations satisfied by ( X , α ) . Both constructions are shown to be functorial. Our main result is that the restrictions of free and cofree to, respectively, preformations of languages and to quotients A * / C of A * with respect to a congr…
Einklassige Geschlechter totalpositiver quadratischer Formen in totalreellen algebraischen Zahlkörpern
1971
Abstract It is proved that totally positive quadratic forms with three or more variables and class number h = 1 exist only in a finite number of algebraic number fields. Each field allows only a finite number of such forms with bounded scale. To prove this, upper estimates for all local factors in Siegel's analytic formula are constructed by calculating explicitly numbers of solutions of quadratic congruences.
Triangular irreducibility of congruences in quasivarieties
2014
Certain forms of irreducibility as well as of equational definability of relative congruences in quasivarieties are investigated. For any integer \({m \geqslant 3}\) and a quasivariety Q, the notion of an m-triangularily meet-irreducible Q-congruence in the algebras of Q is defined. In Section 2, some characterizations of finitely generated quasivarieties involving this notion are provided. Section 3 deals with quasivarieties with equationally definable m-triangular meets of relatively principal congruences. References to finitely based quasivarieties and varieties are discussed.
Formations of Monoids, Congruences, and Formal Languages
2015
The main goal in this paper is to use a dual equivalence in automata theory started in [25] and developed in [3] to prove a general version of the Eilenberg-type theorem presented in [4]. Our principal results confirm the existence of a bijective correspondence between three concepts; formations of monoids, formations of languages and formations of congruences. The result does not require finiteness on monoids, nor regularity on languages nor finite index conditions on congruences. We relate our work to other results in the field and we include applications to non-r-disjunctive languages, Reiterman s equational description of pseudovarieties and varieties of monoids.
Coordinates and frames from the causal point of view
2006
Lorentzian frames may belong to one of the 199 causal classes. Of these numerous causal classes, people are essentially aware only of two of them. Nevertheless, other causal classes are present in some well-known solutions, or present a strong interest in the physical construction of coordinate systems. Here we show the unusual causal classes to which belong so familiar coordinate systems as those of Lema{\^{\i}}tre, those of Eddington-Finkelstein, or those of Bondi-Sachs. Also the causal classes associated to the Coll light coordinates (four congruences of real geodetic null lines) and to the Coll positioning systems (light signals broadcasted by four clocks) are analyzed. The role that th…
The parameterized local deduction theorem for quasivarieties of algebras and its application
1996
Let τ be an algebraic type. To each classK of τ-algebras a consequence relation ⊧ K defined on the set of τ-equations is assigned. Some weak forms of the deduction theorem for ⊧ K and their algebraic counterparts are investigated. The (relative) congruence extension property (CEP) and its variants are discussed.CEP is shown to be equivalent to a parameter-free form of the deduction theorem for the consequence ⊧ K .CEP has a strong impact on the structure ofK: for many quasivarietiesK,CEP implies thatK is actually a variety. This phenomenon is thoroughly discussed in Section 5. We also discuss first-order definability of relative principal congruences. This property is equivalent to the fact…
Relative principal congruences in congruence-modular quasivarieties
1998
The problem of definability of relative principal congruences in relatively congruence modular (RCM) quasivarieties is investigated. The RCM quasivarieties are characterized in terms of parameterized families of finite sets of pairs of terms which define relative principal congruences.
Periodicity vectors for labelled trees
2003
AbstractThe concept of a periodicity vector is introduced in the context of labelled trees, and some new periodicity theorems are obtained. These results constitute generalizations of the classical periodicity theorem of Fine and Wilf for words. The concept of a tree congruence is also generalized and the isomorphism between the lattice of tree congruences and the lattice of unlabelled trees (prefix codes) is established.